//
// Created by mac on 2023/12/1.
//

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

// 反转链表
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

// 方法一：边迭代、边逆置
class Solution
{
public:
    ListNode* reverseList(ListNode* head)
    {
        if(!head) return nullptr;
        // 1、初始化
        ListNode* n1 = nullptr;
        ListNode* n2 = head;
        ListNode* n3 = head->next;
        // 2、逆置
        while(n2)
        {
            n2->next = n1;
            n1 = n2;
            n2 = n3;
            if(n3) n3 = n3->next;
        }
        // 3、返回值
        return n1;
    }
};


// 方法二：头插
class Solution
{
public:
    ListNode* reverseList(ListNode* head)
    {
        // 1、初始化
        ListNode* cur = head, *newHead = nullptr;
        // 2、头插
        while(cur)
        {
            ListNode* next = cur->next;
            cur->next = newHead;
            newHead = cur;
            cur = next;
        }
        // 3、返回值
        return newHead;
    }
};

// 判断回文链表
class Solution
{
private:
    ListNode* ReverseList(ListNode* head)
    {
        if(!head) return nullptr;
        ListNode* n1 = nullptr, *n2 = head, *n3 = head->next;
        while(n2)
        {
            n2->next = n1;
            n1 = n2;
            n2 = n3;
            if(n3) n3 = n3->next;
        }
        return n1;
    }

public:
    bool isPalindrome(ListNode* head)
    {
        // 1、找到中间节点
        ListNode* fast, *slow;
        fast = slow = head;
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        // 2、逆置后半段链表
        ListNode* half = ReverseList(slow);
        // 3、比较前后部分链表
        while(head && half)
        {
            if(head->val != half->val) return false;
            head = head->next;
            half = half->next;
        }
        // 4、返回值
        return true;
    }
};

// 删除排序链表中的重复元素I
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution
{
public:
    ListNode* deleteDuplicates(ListNode* head)
    {
        // 0、特殊情况处理（保证链表至少有两个节点才做处理）
        if(!head || !head->next) return head;
        // 1、初始化
        ListNode* newHead, *tail;
        newHead = tail = new ListNode(); //哨兵位头节点
        ListNode* n1 = head;
        ListNode* n2 = head->next; //n1、n2保持相邻距离
        // 2、删除重复元素
        while(n2)
        {
            if(n1->val != n2->val)
            {
                tail->next = n1;
                tail = n1;
            }
            else
            {
                while(n2 && n2->val == n1->val)
                {
                    n2 = n2->next;
                }
            }
            n1 = n2;
            if(n2) n2 = n2->next;
        }
        tail->next = n1; //处理新链表最后一个节点
        // 3、返回值
        return newHead->next;
    }
};

// 删除排序链表中的重复元素II
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution
{
public:
    ListNode* deleteDuplicates(ListNode* head)
    {
        // 0、特殊情况处理（保证链表至少有两个节点才做处理）
        if(head == nullptr || head->next == nullptr) return head;
        // 1、初始化
        ListNode* newHead, *tail;
        newHead = tail = head;//新链表第一个节点为 head
        head = head->next;    //旧链表从第二个节点开始遍历
        tail->next = nullptr; //设置新链表中第一个节点的 next 为空
        // 2、删除重复元素
        while(head)
        {
            ListNode* cur = head;
            head = head->next;
            if(cur->val != tail->val)
            {
                tail->next = cur;
                tail = cur;
                tail->next = nullptr;
            }
        }
        // 3、返回值
        return newHead;
    }
};

// 随机链表的复制
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution
{
public:
    Node* copyRandomList(Node* head)
    {
        // 1、拷贝节点到原节点的后面
        Node* cur = head;
        while(cur)
        {
            // 初始化
            Node* copy = new Node(cur->val);
            Node* next = cur->next;
            // 链接
            cur->next = copy;
            copy->next = next;
            // 更新cur
            cur = next;
        }
        // 2、处理拷贝节点的 random 指针
        cur = head;
        while(cur)
        {
            Node* copy = cur->next;
            if(cur->random)
                copy->random = cur->random->next;
            // 继续迭代原链表的下一个节点
            cur = cur->next->next;
        }
        // 3、拆解链表
        Node* newHead, *tail; //创造一个哨兵位头节点
        newHead = tail = new Node(0);
        cur = head;
        while(cur)
        {
            // 初始化
            Node* copy = cur->next;
            Node* next = cur->next->next;
            // 尾插拷贝节点到新链表中
            tail->next = copy;
            tail = copy;
            tail->next = nullptr;
            // 处理原链表节点
            cur->next = next;
            cur = next;
        }
        // 4、返回值
        return newHead->next;
    }
};

